/**
 * FileName: TestBSTRandomizedInsert.c
 * -------------------------------------------------------------
 * - 随机插入
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//见Item.h
typedef struct Item* Item;
typedef char Key;
typedef int Value;
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B) (A < B)
#define eq(A, B) (A == B)
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

struct Item {
    Key key;
    Value value;
};

typedef struct STnode* link;

struct STnode {
    Item item;
    link l;
    link r;
    int N;
};

link head;
link z;

/***********************************函数声明*******************************/
int size(link);
void update_N(link h);
link NEW(Item, link, link, int);
link rotL(link);
link rotR(link);
link insertR(link, Item);
link insertT(link, Item);
link insertR2(link, Item);


void STinit();
int STcount();
void STinsert(Item);

/***********************************辅助函数部分*******************************/
link NEW(Item item, link l, link r, int N) {
    link x = malloc(sizeof(*x));
    x->item = item;
    x->l = l;
    x->r = r;
    x->N = N;
    return x;
}

int size(link h) {
    if (h == z) {
        return 0;
    }else {
        return h->N;
    }
}

void update_N(link h) {
    if (h != z) {
        h->N = size(h->l)+size(h->r)+1;
    }
}

/**
 * Program 12.11 Rotations in BSTs
 * ---------------------------------------------------------------------------------------------------------
 * These twin routines perform the rotation operation on a BST.
 * A right rotation makes the old root the right subtree of the new root (the old left subtree of the root).
 * A left rotation makes the old root the left subtree of the new root (the old right subtree of the root).
 *
 * For implementations where a count field is maintained in the nodes
 * (for example, to support `select`, as we will see in Section 14.9),
 * we need also to exchange the `count` fields in the nodes involved in the rotation (see Exercise 12.72).
 * ---------------------------------------------------------------------------------------------------------
 * 右旋
 * @param h
 * @return
 * ---------------------------------------------------------------------------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的左孩子
 *
 * 显然有：h的键大于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->l;
 * - 新根的右孩子节点x->r;
 *
 * 右旋的本质是将旧根的左链接逆向
 */
link rotR(link h) {
    link x = h->l;
    h->l = x->r;
    x->r = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * 左旋
 * @param h
 * @return
 * -----------------------------------------
 * 涉及3个链接和两个节点
 *
 * 这两个节点分别是：
 * - 旧根h
 * - 新根x，即h的右孩子
 *
 * 显然有：h的键小于等于x的键
 *
 * 这3个链接分别是：
 * - 原指向旧根的链接；
 * - 旧根指向新根的链接h->r;
 * - 新根的左孩子节点x->r;
 *
 * 左旋的本质是将旧根的右链接逆向
 */
link rotL(link h) {
    link x = h->r;
    h->r = x->l;
    x->l = h;
    update_N(h);
    update_N(x);
    return x;
}

/**
 * Program 12.12 Root insertion in BSTs
 * ----------------------------------------------------------------------------------
 * With the rotation functions in Program 12.11,
 * a recursive function that inserts a new node at the root of a BST is immediate:
 * - Insert the new item at the root in the appropriate subtree,
 * - then perform the appropriate rotation to bring it to the root of the main tree.
 * ----------------------------------------------------------------------------------
 * 在根部插入递归版
 * @param h 主树的根
 * @param v 待插入项
 * @return
 */
link insertT(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    if (less(v, key(h->item))) {
        h->l = insertT(h->l, item);
        h = rotR(h);
    }else {
        h->r = insertT(h->r, item);
        h = rotL(h);
    }
    return h;
}

/**
 * 在底部插入项
 * @param h
 * @param item
 * @return
 * -------------------------------------------
 * insertT是insertR的自适应版本
 *
 */
link insertR(link h, Item item) {
    if (h == z) {
        return NEW(item, z, z, 1);
    }
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR(h->l, item);
    }else {
        h->r = insertR(h->r, item);
    }
    update_N(h);
    return h;
}

/**
 * Program 13.2 Randomized BST insertion (递归版)
 * -----------------------------------------------------------------------------------
 * 在向一棵包含 N 个节点的 BST 中插入新项时，
 * 我们希望“以概率 1/(N+1) 将新节点插入到根部”，
 * 否则按普通 BST 插入规则递归下去。
 *
 * 概率推导：
 *   令 U = rand() / RAND_MAX ∈ [0,1)，
 *   则事件 U < 1/(N+1) 发生的概率恰好为 1/(N+1)。
 *
 * 实现技巧：
 *   为避免浮点运算，也可以写成
 *     rand() < RAND_MAX/ (N + 1)
 *   此时两边均为整数比较，等价于上面的浮点判断。
 * ------------------------------------------------------------------------------------
 * 参数：
 * @param h    - 当前子树根节点指针（z 表示空树哨兵）。
 * @param item - 待插入的记录。
 *
 * @return     - 插入新节点后的子树根指针。
 */
link insertR2(link h, Item item) {
    // 空树——直接创建新节点，子树规模为 1
    if (h == z) {
        return NEW(item, z, z, 1);
    }

    // 以 1/(h->N + 1) 的概率，使用“根插入”策略
    // 等价于：((double)rand() / RAND_MAX < 1.0 / (h->N + 1)
    if (rand() < RAND_MAX/(h->N + 1)) {
        // 根部插入
        return insertT(h, item);
    }

    // 否则，底部插入
    Key v = key(item);
    Key t = key(h->item);
    if (less(v, t)) {
        h->l = insertR2(h->l, item);
    } else {
        h->r = insertR2(h->r, item);
    }

    // 更新当前子树节点计数
    update_N(h);
    return h;
}

/***********************************接口部分*******************************/
void STinit() {
    z = NEW(NULLitem, 0, 0, 0);
    head = z;
}

int STcount() {
    return head->N;
}

/**
 * STinsert
 * @param item
 * -----------------------------------------------------------------------
 * - 随机选择在底部和根部插入
 */
void STinsert(Item item) {
    // 插入(随机版本)
    head = insertR2(head, item);
}

/***********************************测试部分*******************************/
Item create_item(Key key, Value value) {
    Item x = malloc(sizeof(*x));
    x->key = key;
    x->value = value;
    return x;
}

void test_insert_randomized() {
    STinit();
    assert(STcount() == 0);

    STinsert(create_item('L', 1));
    STinsert(create_item('G', 2));
    STinsert(create_item('P', 3));
    STinsert(create_item('E', 4));
    STinsert(create_item('I', 5));
    STinsert(create_item('M', 6));
    STinsert(create_item('X', 7));
    STinsert(create_item('C', 8));
    STinsert(create_item('H', 9));
    STinsert(create_item('N', 10));
    STinsert(create_item('S', 11));
    STinsert(create_item('A', 12));
    STinsert(create_item('R', 13));
    assert(STcount() == 13);
}

int main(int argc, char *argv[]) {
    test_insert_randomized();
    return 0;
}

